package main

import (
	"fmt"
	"math/rand"
	"time"
)

const MaxLevel = 32
const p = 0.5

func main() {
	s := Constructor()
	s.Add(1)
	s.Add(2)
	s.Add(3)
	s.Search(0)
	s.Add(4)
	s.Search(1)
	s.Erase(0)
	s.Erase(1)
	r := s.Search(1)
	fmt.Println(r)
}

type Skiplist struct {
	Head  *Node
	Level int
}

type Node struct {
	Key      int
	Forwards []*Node
}

func randLevel() int {
	rand.Seed(time.Now().UnixNano())
	level := 1

	for rand.Float64() < p && level < 32 {
		level++
	}
	return level
}

func Constructor() *Skiplist {
	return &Skiplist{Level: 1, Head: &Node{Forwards: make([]*Node, MaxLevel)}}
}

func (s *Skiplist) Search(key int) bool {
	x := s.Head
	for i := s.Level - 1; i >= 0; i-- {
		for x.Forwards[i] != nil && x.Forwards[i].Key < key {
			x = x.Forwards[i]
		}
	}

	x = x.Forwards[0]
	if x != nil && x.Key == key {
		return true
	} else {
		return false
	}
}

func (s *Skiplist) Add(key int) bool {
	x := s.Head
	update := make([]*Node, MaxLevel)
	for i := s.Level - 1; i >= 0; i-- {
		for x.Forwards[i] != nil && x.Forwards[i].Key < key {
			x = x.Forwards[i]
		}
		update[i] = x
	}
	level := randLevel()
	node := &Node{Key: key, Forwards: make([]*Node, level)}
	if level > s.Level {
		for i := s.Level; i < level; i++ {
			update[i] = s.Head
		}
		s.Level = level
	}

	for i := level - 1; i >= 0; i-- {
		node.Forwards[i] = update[i].Forwards[i]
		update[i].Forwards[i] = node
	}
	return true
}

func (s *Skiplist) Erase(key int) bool {
	x := s.Head
	flag := false
	for i := s.Level - 1; i >= 0; i-- {
		for x.Forwards[i] != nil {
			if x.Forwards[i].Key == key {
				tmp := x.Forwards[i]
				x.Forwards[i] = tmp.Forwards[i]
				tmp.Forwards[i] = nil
				flag = true
			} else if x.Forwards[i].Key > key {
				break
			} else {
				x = x.Forwards[i]
			}
		}
	}

	return flag
}
